package class04;

public class MyCode01_ReverseList {

    public static class Node {
        public int value;
        public Node next;

        public Node(int data) {
            value = data;
        }
    }

    public static class DoubleNode {
        public int value;
        public DoubleNode last;
        public DoubleNode next;

        public DoubleNode(int data) {
            value = data;
        }
    }

    public static Node reverseLinkedList(Node head) {
        Node pre = null;//上一个节点
        Node next = null;//下一个节点

        while (head != null) {
            next = head.next;//head的下一个位置给next记住一下
            head.next = pre;//head指向上一个指针位置
            pre = head;//pre去到当前head位置
            head = next;//head往下走
        }
        return pre;//最后，pre变成翻转后的头，返回
    }

    public static DoubleNode reverseDoubleList(DoubleNode head) {
        DoubleNode pre = null;//上一个节点
        DoubleNode next = null;//下一个节点
        while (head != null) {
            next = head.next;//head的下指针位置给next记住一下
            head.next = pre;//head的下指针 指向 上指针位置
            head.last = next;//head的上指针变成原来head的下指针
            pre = head;//pre去到当前head位置
            head = next;//head往下走
        }
        return pre;
    }

    // for test
    public static DoubleNode generateRandomDoubleList(int len, int maxValue) {
        int size = len;
        if (size == 0) {
            return null;
        }
        size--;
        DoubleNode head = new DoubleNode((int) (Math.random() * (maxValue + 1)));
        DoubleNode pre = head;//记录位置游标
        while (size != 0) {
            DoubleNode cur = new DoubleNode((int) (Math.random() * (maxValue + 1)));
            pre.next = cur;
            cur.last = pre;
            pre = cur;//更新当前位置
            size--;
        }
        return head;
    }

    public static void main(String[] args) {
//        单向链
//        Node n1 = new Node(1);
//        n1.next = new Node(2);
//        n1.next.next = new Node(3);
//        print(n1);
//        System.out.println();
//        print(reverseLinkedList(n1));

        DoubleNode dn = generateRandomDoubleList(5, 9);
        print(dn);
        System.out.println();
        print(reverseDoubleList(dn));
    }
    public static void print(Node head) {
        while (head != null) {
            System.out.print(head.value + " ");
            head = head.next;
        }
    }

    public static void print(DoubleNode head) {
        while (head != null) {
            System.out.print(head.value + " ");
            head = head.next;
        }
    }

}